{\magonebf 4.6 Sorted Sequences  (sortseq)}

An instance $S$ of the data type $sortseq$ is a sequence of items ($seq\_item$).
Every item contains a key from a linearly ordered data type $K$ , called the 
key type of $S$, and an information from a data type $I$, called the information
type  of $S$. The number of items in $S$ is called the size of $S$. A sorted 
sequence of size zero is called empty. We use $<k,i>$ to denote a $seq\_item$ 
with key $k$ and information $i$ (called the information associated with key 
$k$). For each $k \in K$ there is at most one item $<k,i> \in S$. 

The linear order on $K$ may be time-dependent, e.g., in an algorithm that
sweeps an arrangement of lines by a vertical sweep line we may want to order
the lines by the y-coordinates of their intersections with the sweep line. 
However, whenever an operation (except of reverse\_items) is applied to a 
sorted sequence $S$, the keys of $S$ must form an increasing sequence according
to the currently valid linear order on $K$. For operation reverse\_items this 
must hold after the execution of the operation.



\bigskip
{\bf 1. Declaration of a sorted sequence type}


\decltwo sortseq K I 

introduces a new data type with name \name\ consisting of all 
sorted sequences with key type $K$ and information type $I$.


\bigskip
{\bf 2. Creation of a sorted sequence }


\create S {}

creates an instance \var\ of type \name\ and initializes it to the empty 
sorted sequence.


\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\smallskip
\+\op K         key         {seq\_item\ it}     
                               {returns the key of item $it$}
\+\nop                         {\precond $it$ is an item in \var.}
\smallskip
\+\op I         inf         {seq\_item\ it}     
                               {returns the information of item $it$}
\+\nop                         {\precond $it$ is an item in \var.}
\smallskip
\+\op seq\_item lookup      {K\ k}    
                               {returns the item with key $k$ }
\+\nop                         {( nil if no such item exists in \var\ )}
\smallskip
\+\op seq\_item insert      {K\ k, I\ i}
                               {associates information $i$ with key $k$: If}
\+\nop                         {there is an item $<k,j>$ in \var\ then $j$ is}
\+\nop                         {replaced by $i$, else a new item $<k,i>$ is}
\+\nop                         {added to \var. In both cases the item is }
\+\nop                         {returned.}
\smallskip
\+\op seq\_item insert\_at\_item  {seq\_item\ it,\ K\ k, I\ i} {}
\+\nop                         {Like insert($k,i$), the item $it$ gives the}
\+\nop                         {position of the item $<k,i>$ in the sequence}
\+\nop                         {\precond $it$ is an item in $S$ with either}
\+\nop                         {key($it$) is maximal with key($it) < k$ or}
\+\nop                         {key($it$) is minimal with key$(it) > k$}
\smallskip
\+\op seq\_item locate      {K\ k}    
                               {returns the item $<k\',i>$ in \var\ such that}
\+\nop                         {$k\'$ is minimal with $k\' >= k$ ( nil if no }
\+\nop                         {such item exists).}
\smallskip
\+\op seq\_item succ        {seq\_item\ it}      
                              {returns the successor item of it, i.e., the }
\+\nop                        {item $<k,i>$ in \var\ such that $k$ is minimal}
\+\nop                        {with $k > key(it)$ (nil if no such item exists).}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip 
\+\op seq\_item pred        {seq\_item\ it}      
                              {returns the predecessor item of $it$, i.e., the}
\+\nop                        {item $<k,i>$ in \var\ such that $k$ is maximal }
\+\nop                        {with $k < key(it)$ (nil if no such item exists).}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op seq\_item max         {}       
                               {returns the item with maximal key}
\+\nop                         {(nil if \var\ is empty).}
\smallskip
\+\op seq\_item min         {}       
                               {returns the item with minimal key}
\+\nop                         {(nil if \var\ is empty).}
\smallskip
\+\op void      del\_item   {seq\_item\ it}    
                               {removes the item $it$ from \var.}
\+\nop                         {\precond $it$ is an item in \var.}
\smallskip
\+\op void      del         {K\ k}    
                               {removes the item with key $k$ from \var}
\+\nop                         {(null operation if no such item exists).}
\smallskip
\+\op void      change\_inf {seq\_item\ it,\ I\ i} 
                               {makes $i$ the information of item $it$.}
\+\nop                         {\precond $it$ is an item in \var.}
\smallskip
\+\op void      reverse\_items {seq\_item\ a,\ seq\_item\ b}  {}
\+\nop                     {the subsequence of $S$ from $a$ to $b$ is reversed.}
\+\nop                     {\precond $a$ appears before $b$ in $S$.}
\smallskip
\+\op void      split {seq\_item\ it,\ sortseq\&\ S_1,\ sortseq\&\ S_2}  {}
\+\nop                {splits $S$ at item $it$ into sequences $S_1$ and $S_2$}
\+\nop                {and makes $S$ empty. More precisely, if}
\+\nop                {$S = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
\+\nop                {$S1 = x_1,\dots,x_{k-1},it$ and $S2 = x_{k+1},\dots,x_n$}
\+\nop                {\precond $it$ is an item in $S$. }
\smallskip
\+\op sortseq\& conc {sortseq\&\ S_1} 
                     {appends $S_1$ to $S$, makes $S_1$ empty and} 
\+\nop               {returns $S$. \precond }
\+\nop               {$S$.key($S$.max()) $\le$ $S_1$.key($S_1$.min()).}
\smallskip
\+\op void      clear       {}       
                               {makes \var\ the empty sorted sequence.}
\smallskip
\+\op int       size        {}       
                               {returns the size of \var.}
\smallskip
\+\op bool      empty       {}       
                              {returns true if \var\ is empty, false otherwise.}

\bigskip
{\bf 4. Iteration}


{\bf forall\_seq\_items}($i,S$) 
$\{$  ``the items of $S$ are successively assigned to $i$''  $\}$



\bigskip
{\bf 5. Implementation}
\medskip
Sorted sequences are implemented by (2,4)-trees. Operations lookup, locate, 
insert, del, split, conc take time $O(\log n)$, operations succ, pred, max, 
min, key, inf, insert\_at\_item and del\_item take time $O(1)$. Clear takes 
time $O(n)$ and reverse\_items $O(\ell)$, where $\ell$ is the length of the 
reversed subsequence. The space requirement is $O(n)$. Here $n$ is the current 
size of the sequence.


\bigskip
{\bf 6. Example }
\medskip
\input prog/sortseq.prog

